package com.leetcode.dynamic_programming;

/**
 * @author Dennis Li
 * @date 2020/7/19 9:50
 */
public class Rob2_213 {
    public int rob(int[] nums) {
        // 题意看似复杂，其实就是考虑两段路程0 ~ n-1和1~n，并取其最大值即可
        int len = nums.length;
        // 一定要注意边界条件的判定
        if (len <= 2) return len == 0 ? 0 : len == 1 ? nums[0] : Math.max(nums[0], nums[1]);
        int[] dp1 = new int[len - 1];
        int[] dp2 = new int[len - 1];
        dp1[0] = nums[0];
        dp1[1] = Math.max(nums[0], nums[1]);
        dp2[0] = nums[1];
        dp2[1] = Math.max(nums[2], nums[1]);
        for (int i = 2; i < len - 1; i++) {
            dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
            dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i + 1]);
        }
        return Math.max(dp1[len - 2], dp2[len - 2]);
    }

    public int rob2(int[] nums) {
        int n = nums.length;
        if (n <= 2) return n == 0 ? 0 : n == 1 ? nums[0] : Math.max(nums[0], nums[1]);
        return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
    }

    private int rob(int[] nums, int first, int last) {
        // 不需要用数组
        // 可以通过状态压缩来规避问题，只需要记录两个状态即可
        int pre2 = 0, pre1 = 0;
        for (int i = first; i <= last; i++) {
            int cur = Math.max(pre1, pre2 + nums[i]);
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }


    public int rob3(int[] nums) {
        if (nums.length == 1) return nums[0];
        int max1 = rob3(nums, 0, nums.length - 1);
        int max2 = rob3(nums, 1, nums.length);
        return Math.max(max1, max2);
    }

    private int rob3(int[] nums, int left, int right) {
        int pre1 = 0, pre2 = 0;
        for (int i = left; i < right; i++) {
            int cur = pre2 + nums[i];
            pre2 = pre1;
            pre1 = Math.max(pre1, cur);
        }
        return pre1;
    }

}
